package 其他.博弈;

import org.junit.Test;

/*
    评论达人：
        先手的人可以控制自己拿到全部奇数组或者偶数组，
        所以必然能够选择较大的一组，那么就是必胜的

    思路：每个cur管好自己就行，为啥连起来能用，不知道
         看图写

    按顺序'干中单'
    千万不可跳着先'单'!
 */
public class 太难理解_纯背_两个聪明人拿石头877 {
    @Test
    public void test() {
        int[] a  = {3,9,1,2};
        System.out.println(stoneGame(a));
    }

    public boolean stoneGame(int[] p) {
        int n = p.length;
        int[][][] dp = new int[n][n][2];

        //base[i==j]就一个元素
        for (int i = 0; i < n; i++) {
            //先手
            dp[i][i][0] = p[i];
            //后手
            dp[i][i][1] = 0;
        }

        //斜着走: 遍历第一行的每一列的单个元素做起点, 每个下到头即可
        for (int I = 1; I < n; I++) {
            int i=0,j=I;
            while(j<n){
//                //fir
//                dp[i][j][0] = Math.max(p[i]+dp[i+1][j][1], p[j]+dp[i][j-1][1]);
//                //sec不能用max选择，因为是根据上方fir固定死的
//                if()
//                dp[i][j][1] = Math.max(dp[i+1][j][0], dp[i][j-1][0]);

                //合在一起写方便知道fir选的哪个，要不还得if==判断,太多公式不愿看
                if(p[i]+dp[i+1][j][1] >= p[j]+dp[i][j-1][1]){
                    dp[i][j][0] = p[i]+dp[i+1][j][1];
                    dp[i][j][1] = dp[i+1][j][0];
                }else{
                    dp[i][j][0] = p[j]+dp[i][j-1][1];
                    dp[i][j][1] = dp[i][j-1][0];
                }
                //斜着走
                i++;j++;
            }
        }
        System.out.println(dp[0][n-1][0] + "," +dp[0][n-1][1]);
        return dp[0][n-1][0]>dp[0][n-1][1];
    }
}
